package algorithms.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * 基数排序（桶排序）
 *   思路：
 *      1.找到最大值，判断最大值的位数（默认10进制）
 *      2.申请0~9共10个桶（10进制）
 *      3.从左到右，将每一位的值根据个位放入对应的桶中，从左向右的桶中按先进先出顺序倒出数据。
 *      4.十位重复步骤3，千位重复步骤3。。。。直到做到最大值的位数结束。
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr100(15);
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        // 1.找到最大值,判断最大值的位数（默认10进制）
        int max = getArrMax(arr);
        int digit = getDigit(max);
        // 2.申请0~9共10个桶（10进制）
        Map<Integer, Queue<Integer>> buckets = new HashMap<>();
        for (int i = 0;i < 10;i++)
            buckets.put(i,new LinkedBlockingDeque<Integer>());
        // 3.从左到右，将每一位的值根据个位放入对应的桶中，从左向右的桶中按先进先出顺序倒出数据。
        // 4.十位重复步骤3，千位重复步骤3。。。。直到做到最大值的位数结束。
        for (int count = 1 ; digit >= count; count++) {
            // 将每一位的值根据 位数的值 放入对应的桶中
            for (int j = 0; j< arr.length; j++) {
                buckets.get(getDigitNum(arr[j],count)).add(arr[j]);
            }
            // 从左向右的桶中按先进先出顺序倒出数据。
            for (int j = 0,index = 0;j<buckets.keySet().size();j++) {
                Queue<Integer> queue = buckets.get(j);
                while (!queue.isEmpty()) {
                    arr[index++] = queue.poll();
                }
            }
        }
    }

    /**
     * 获取数组中的最大值
     *
     * @param arr
     * @return
     */
    public static int getArrMax(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int e : arr){
            max = Math.max(e,max);
        }
        return max;
    }

    /**
     * 获取一个数有几位
     *
     * @param num : 判断数值
     * @return digit : 该数值的位数
     */
    public static int getDigit(int num) {
        int digit = 0;
        while (num != 0) {
            num = num / 10;
            digit++;
        }
        return digit;
    }

    /**
     * 获取该数指定位数上的值
     *
     * @param num : 数值
     * @param digit : 取第几位
     * @return v : 该位上的数值
     */
    public static int getDigitNum(int num,int digit) {
        int v = -1;
        if (digit < 0)
            return v;
        for (int i = 0 ;i < digit;i++) {
             v = num % 10;
             num /= 10;
        }
        return v;
    }


}
